package com.zp.self.module.level_4_算法练习.算法.动态规划;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_322_零钱兑换 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_322_零钱兑换().coinChange(new int[]{1, 2, 5},11));
    }

    /**
    题目：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
     计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     你可以认为每种硬币的数量是无限的。

     示例 1：
     输入：coins = [1, 2, 5], amount = 11
     输出：3
     解释：11 = 5 + 5 + 1

     示例 2：
     输入：coins = [2], amount = 3
     输出：-1

     示例 3：
     输入：coins = [1], amount = 0
     输出：0

    分析：【P 💓💓💓】
       1.动态规划+递归：f(n) = min(f(n-coins[0]),f(n-coins[1]......f(n-coins[len-1])) +1
       2.动态规划+迭代：dp[]  动态规划三步曲  确实好用啊
                 1. 定义数组元素的含义:每一个总值对应需要的最少硬币
                 2. 找出数组元素之间的关系式--状态方程:dp[n] = min(f(n-coins[0]),f(n-coins[1]......f(n-coins[len-1])) +1
                 3. 找出初始值:dp[coins[i]] =1
                --执行用时：15 ms, 在所有 Java 提交中击败了34.05%的用户

    边界值 & 注意点：
       1.币值太大了
     **/
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,-1);
        int current=1;
        dp[0]=0;
        while (current<=amount){
            int min = Integer.MAX_VALUE;
            for (int coin : coins){
                if(coin>current)continue;
                if(dp[current-coin]==-1)continue;
                min= Math.min(min,dp[current-coin]);
            }
            if(min!=Integer.MAX_VALUE)dp[current]=min+1;
            current++;
        }
        return dp[amount];
    }
}
